package pers.qianyu.month_202101.date_20210121;

import java.util.*;

/**
 * 42. 接雨水
 * https://leetcode-cn.com/problems/trapping-rain-water/submissions/
 *
 * @author mizzle rain
 * @date 2021年1月21日17:37:34
 */
public class TrappingRainWater {
    public int trap(int[] height) {
        int len = height.length;
        if (len < 2) return 0;
        Deque<Integer> st = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < len; i++) {
            int last = 0;
            while (!st.isEmpty() && height[st.getLast()] <= height[i]) {
                int t = st.pollLast();
                int h = height[t] - last, w = i - t - 1;
                res += w * h;
                last = height[t];
            }
            if (!st.isEmpty()) res += (height[i] - last) * (i - st.getLast() - 1);
            st.addLast(i);
        }
        return res;
    }
}